package arithmetic2.day10;

/*
    在一个只有0、1组成的二维数组里面，每个数只能跟上下左右4个数相连，
    每块1组成的部分为一个孤岛，求数组中孤岛的个数
 */
public class Islet {
    public static void main(String[] args) {
        int arr[][]={
                {0,0,1,0,1,0,0},
                {1,1,1,0,1,0,0},
                {1,0,0,0,0,0,0},
                {1,0,0,0,1,0,0},
                {0,0,1,0,0,0,0}
        };
        System.out.println(islet(arr));
    }

    public static int islet(int arr[][]) {
        int res = 0;
        int N = arr.length;
        int Y = arr[0].length;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < Y; j++) {
                if (arr[i][j] == 1) {
                    res++;
                    infect(arr, i, j, N, Y);
                }
            }
        }
        return res;
    }

    public static void infect(int arr[][], int i, int j, int N, int Y) {
        if (i < 0 || i >= N || j < 0 || j >= Y || arr[i][j] != 1) {
            return;
        }
        arr[i][j] = 2;
        infect(arr,i-1,j,N,Y);
        infect(arr,i,j+1,N,Y);
        infect(arr,i+1,j,N,Y);
        infect(arr,i,j-1,N,Y);
    }
}
